package 力扣算法练习.main1.part1;

import java.util.*;

public class day6 {
    /*
    给你一个包含 n 个整数的数组nums，判断nums中是否存在三个元素
    a，b，c ，使得a + b + c = 0 ？请你找出所有和为 0 且不重复的三元组。
    注意：答案中不可以包含重复的三元组。
    https://leetcode.cn/problems/3sum
     */
    //错误代码
/*    public List<List<Integer>> threeSum(int[] nums) {
        //采用双指针的方式解,首先指向两个元素然后找第三个元素相加
        List<List<Integer>> result=new ArrayList<>();
        if (nums.length<3)return result;
        Arrays.sort(nums);
        int t=0;
        for (int i = 0; i < nums.length-1; i++) {
            for (int j = i+2; j < nums.length ; j++) {
                if (nums[i]+nums[i+1]+nums[j]==0){
                    if (nums[i]==0&&nums[i+1]==0&&t!=0)continue;//排除全为零的情况
                    if (nums[i]==0&&nums[i+1]==0)t++;
                    List<Integer> temp=new ArrayList<>();
                    temp.add(nums[i]);
                    temp.add(nums[i+1]);
                    temp.add(nums[j]);
                    result.add(temp);
                }
            }
        }
        return result;
    }*/
    //官方解
    class Solution {
        public List<List<Integer>> threeSum(int[] nums) {
            int n = nums.length;
            Arrays.sort(nums);
            List<List<Integer>> ans = new ArrayList<List<Integer>>();
            // 枚举 a
            for (int first = 0; first < n; ++first) {
                // 需要和上一次枚举的数不相同
                if (first > 0 && nums[first] == nums[first - 1]) {
                    continue;
                }
                // c 对应的指针初始指向数组的最右端
                int third = n - 1;
                int target = -nums[first];
                // 枚举 b
                for (int second = first + 1; second < n; ++second) {
                    // 需要和上一次枚举的数不相同
                    if (second > first + 1 && nums[second] == nums[second - 1]) {
                        continue;
                    }
                    // 需要保证 b 的指针在 c 的指针的左侧
                    while (second < third && nums[second] + nums[third] > target) {
                        --third;
                    }
                    // 如果指针重合，随着 b 后续的增加
                    // 就不会有满足 a+b+c=0 并且 b<c 的 c 了，可以退出循环
                    if (second == third) {
                        break;
                    }
                    if (nums[second] + nums[third] == target) {
                        List<Integer> list = new ArrayList<Integer>();
                        list.add(nums[first]);
                        list.add(nums[second]);
                        list.add(nums[third]);
                        ans.add(list);
                    }
                }
            }
            return ans;
        }
    }


    /*
    给定一个仅包含数字2-9的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。
    给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。
    https://leetcode.cn/problems/letter-combinations-of-a-phone-number
     */
    /*public List<String> letterCombinations(String digits) {
        //遍历字符串将数字对应的字符拼接
        List<String> result=new ArrayList<>();
        if (digits.length()==0)return result;
        String[] letter={"abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
        StringBuilder temp=new StringBuilder();
        //遍历字符串
        int index=0;//控制每一个字符串添加几个字符
        StringBuilder charTemp=new StringBuilder();
        for (int i = 0; i < digits.length(); i++) temp.append(letter[digits.charAt(i)-48]);
        for (int i = 0; i < temp.length(); i++) {
            for (int j = 0; j < temp.length(); j++) {

            }
        }
    }*/
    //官方解
    public List<String> letterCombinations(String digits) {
        List<String> combinations = new ArrayList<String>();
        if (digits.length() == 0) {
            return combinations;
        }
        Map<Character, String> phoneMap = new HashMap<Character, String>() {{
            put('2', "abc");
            put('3', "def");
            put('4', "ghi");
            put('5', "jkl");
            put('6', "mno");
            put('7', "pqrs");
            put('8', "tuv");
            put('9', "wxyz");
        }};
        backtrack(combinations, phoneMap, digits, 0, new StringBuffer());
        return combinations;
    }

    public void backtrack(List<String> combinations, Map<Character, String> phoneMap, String digits, int index, StringBuffer combination) {
        if (index == digits.length()) {
            combinations.add(combination.toString());
        } else {
            char digit = digits.charAt(index);
            String letters = phoneMap.get(digit);
            int lettersCount = letters.length();
            for (int i = 0; i < lettersCount; i++) {
                combination.append(letters.charAt(i));
                backtrack(combinations, phoneMap, digits, index + 1, combination);
                combination.deleteCharAt(index);
            }
        }
    }

}
